|
In computational complexity and optimization the no free lunch theorem is a result that states that for certain types of mathematical problems, the computational cost of finding a solution, averaged over all problems in the class, is the same for any solution method. No solution therefore offers a 'short cut'. In computing, there are circumstances in which the outputs of all procedures solving a particular type of problem are statistically identical. A colourful way of describing such a circumstance, introduced by David Wolpert and William G. Macready in connection with the problems of search〔Wolpert, D.H., Macready, W.G. (1995), No Free Lunch Theorems for Search, Technical Report SFI-TR-95-02-010 (Santa Fe Institute).〕 and optimization,〔Wolpert, D.H., Macready, W.G. (1997), "No Free Lunch Theorems for Optimization," ''IEEE Transactions on Evolutionary Computation'' 1, 67. http://ti.arc.nasa.gov/m/profile/dhw/papers/78.pdf〕 is to say that there is no free lunch. Wolpert had previously derived no free lunch theorems for machine learning (statistical inference).〔Wolpert, David (1996), "“The Lack of A Priori Distinctions between Learning Algorithms," ''Neural Computation'', pp. 1341–1390. 〕 Before Wolpert's article was published, Cullen Schaffer independently proved a restricted version of one of Wolpert's theorems and used it to critique the current state of machine learning research on the problem of induction.〔Schaffer, Cullen (1994), "A conservation law for generalization performance," ''International Conference on Machine Learning,'' H. Willian and W. Cohen, Editors. San Francisco: Morgan Kaufmann, pp.259–265. 〕 In the "no free lunch" metaphor, each "restaurant" (problem-solving procedure) has a "menu" associating each "lunch plate" (problem) with a "price" (the performance of the procedure in solving the problem). The menus of restaurants are identical except in one regard – the prices are shuffled from one restaurant to the next. For an omnivore who is as likely to order each plate as any other, the average cost of lunch does not depend on the choice of restaurant. But a vegan who goes to lunch regularly with a carnivore who seeks economy might pay a high average cost for lunch. To methodically reduce the average cost, one must use advance knowledge of a) what one will order and b) what the order will cost at various restaurants. That is, improvement of performance in problem-solving hinges on using prior information to match procedures to problems.〔〔 In formal terms, there is no free lunch when the probability distribution on problem instances is such that all problem solvers have identically distributed results. In the case of search, a problem instance is an objective function, and a result is a sequence of values obtained in evaluation of candidate solutions in the domain of the function. For typical interpretations of results, search is an optimization process. There is no free lunch in search if and only if the distribution on objective functions is invariant under permutation of the space of candidate solutions.〔Streeter, M. (2003) "Two Broad Classes of Functions for Which a No Free Lunch Result Does Not Hold," ''Genetic and Evolutionary Computation – GECCO 2003'', pp. 1418–1430.〕〔Igel, C., and Toussaint, M. (2004) "A No-Free-Lunch Theorem for Non-Uniform Distributions of Target Functions," ''Journal of Mathematical Modelling and Algorithms'' 3, pp. 313–322.〕〔English, T. (2004) No More Lunch: Analysis of Sequential Search, ''Proceedings of the 2004 IEEE Congress on Evolutionary Computation'', pp. 227–234. http://BoundedTheoretics.com/CEC04.pdf〕 This condition does not hold precisely in practice,〔 but an "(almost) no free lunch" theorem suggests that it holds approximately.〔S. Droste, T. Jansen, and I. Wegener. 2002. "Optimization with randomized search heuristics: the (A)NFL theorem, realistic scenarios, and difficult functions," ''Theoretical Computer Science,'' vol. 287, no. 1, pp. 131–144.〕 ==Overview== Some computational problems are solved by searching for good solutions in a space of candidate solutions. A description of how to repeatedly select candidate solutions for evaluation is called a search algorithm. On a particular problem, different search algorithms may obtain different results, but over all problems, they are indistinguishable. It follows that if an algorithm achieves superior results on some problems, it must pay with inferiority on other problems. In this sense there is no free lunch in search.〔 Alternatively, following Schaffer,〔 search performance is conserved. Usually search is interpreted as optimization, and this leads to the observation that there is no free lunch in optimization.〔 "The 'no free lunch' theorem of Wolpert and Macready," as stated in plain language by Wolpert and Macready themselves, is that "any two algorithms are equivalent when their performance is averaged across all possible problems."〔Wolpert, D.H., and Macready, W.G. (2005) "Coevolutionary free lunches," ''IEEE Transactions on Evolutionary Computation'', 9(6): 721–735〕 The "no free lunch" results indicate that matching algorithms to problems gives higher average performance than does applying a fixed algorithm to all. Igel and Toussaint〔 and English〔 have established a general condition under which there is no free lunch. While it is physically possible, it does not hold precisely.〔 Droste, Jansen, and Wegener have proved a theorem they interpret as indicating that there is "(almost) no free lunch" in practice.〔 To make matters more concrete, consider an optimization practitioner confronted with a problem. Given some knowledge of how the problem arose, the practitioner may be able to exploit the knowledge in selection of an algorithm that will perform well in solving the problem. If the practitioner does not understand how to exploit the knowledge, or simply has no knowledge, then he or she faces the question of whether some algorithm generally outperforms others on real-world problems. The authors of the "(almost) no free lunch" theorem say that the answer is essentially no, but admit some reservations as to whether the theorem addresses practice.〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「No free lunch in search and optimization」の詳細全文を読む スポンサード リンク
|